# Dijkstra算法
# 对于一个无向图，求从某个顶点到其他顶点的最短路径

def Dijkstra(graph, start):
    """
    :param graph: 图
    :param start: 起始顶点
    :return:
    """
    # 初始化
    dist = {}
    prev = {}
    for v in graph.keys():
        dist[v] = float('inf')
        prev[v] = None
    dist[start] = 0
    Q = set(graph.keys())
    while Q:
        # 寻找最小距离的顶点
        u = None
        for v in Q:
            if u is None or dist[v] < dist[u]:
                u = v
        # 删除u
        Q.remove(u)
        # 更新dist
        for v in graph[u]:
            if dist[v] > dist[u] + graph[u][v]:
                dist[v] = dist[u] + graph[u][v]
                prev[v] = u
    return dist, prev